#include <iostream>
#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> result;  // 存放前序遍历结果的容器

    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return result;  // 如果根节点为空，直接返回空的结果
        }
        
        // 访问当前节点
        result.push_back(root->val);
        
        // 递归遍历左子树
        if (root->left != nullptr) {
            preorderTraversal(root->left);
        }
        
        // 递归遍历右子树
        if (root->right != nullptr) {
            preorderTraversal(root->right);
        }
        
        return result;  // 返回前序遍历结果
    }
};

// 测试函数
int main() {
    // 创建二叉树节点
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 创建 Solution 对象
    Solution solution;
    
    // 进行前序遍历
    vector<int> result = solution.preorderTraversal(root);

    // 打印遍历结果
    cout << "Preorder traversal result: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    // 释放二叉树的内存（释放节点）
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}